package E_2024;

import java.util.HashSet;
import java.util.Set;

public class E_100_5 {
    /*
    题目描述
        给定 M 个字符( a-z ) ，从中取出任意字符(每个字符只能用一次)拼接成长度为 N 的字符串，要求相同的字符不能相邻。
        计算出给定的字符列表能拼接出多少种满足条件的字符串，输入非法或者无法拼接出满足条件的字符串则返回 0 。
    输入描述
        给定长度为 M 的字符列表和结果字符串的长度 N ，中间使用空格(" ")拼接。
        0 < M < 30
        0 < N ≤ 5
    输出描述
        输出满足条件的字符串个数。

    输入：
        abc 1
    输出：
        3
    说明：
        给定的字符为 abc ，结果字符申长度为 1 ，可以拼接成 a、b、c ，共 3 种。

    输入：
        dde 2
    输出：
        2
    说明：
        给定的字符为 dde ，果字符串长度为 2 ，可以拼接成 de、ed， 共 2 种。
     */
    public static void main(String[] args) {
        System.out.println(ans1("abc", 1));
        System.out.println(ans1("abc", 2));
        System.out.println(ans1("abc", 3));
        System.out.println(ans1("abcd", 3));
        System.out.println(ans1("aae", 2));
        System.out.println(ans1("aae", 1));
    }
    /*
     abcd
     a b c d
     ab ac ad bc bd cd
     abc abd acd bcd
     a
     a b
     b a
     a b c
     a c b
     b a c
     b c a
     c a b
     c b a
     a b c d
     a b d c
     a c b d
     a c d b
     a d b c
     a d c b
     b a c d
     b a d c
     b c a d
     b c d a
     b d a c
     b d c a
     */
    public static int ans1(String str, int length){
        // 字符选择种数
        int ans1 = 0;
        Set<Character> set = new HashSet<>();
        for (char ch : str.toCharArray()) {
            set.add(ch);
        }
        int x = 1;
        int y = 1;
        for (int i = 0; i < length; i++) {
            x *= (set.size() - i);
            y *= (length - i);
        }
        // 在 set.size 个字符中选择 length 个字符
        ans1 = x / y;
        // 字符排序种数
        int[] temp = new int[length+1];
        temp[0] = 1;
        for (int i = 1; i <= length; i++) {
            temp[i] = i * temp[i-1];
        }
        // 答案为 字符选择方案数 * length个字符有多少种排序方案
        return ans1 * temp[length];
    }
}
